import { Entity } from "../Entity/def/Entity";

export class Pathfinder {

    static findPath(start: number[], target: number[], map: Map<String, Entity>, execLast: boolean) {
        try {
            const graph = this.buildGraph(map, execLast, target)

            const startNode = start[0] * 11 + start[1]; // 起点在邻接矩阵中的索引
            const endNode = target[0] * 11 + target[1];
            const shortestPath = this.dijkstra(graph, startNode, endNode);
            const pathCoordinates = shortestPath.map((nodeIndex) => {
                const x = Math.floor(nodeIndex / 11); // 计算节点在坐标系中的 x 坐标
                const y = nodeIndex % 11; // 计算节点在坐标系中的 y 坐标
                return [x, y];
            });
            return pathCoordinates;
        } catch {
            return undefined;
        }
    }

    static buildGraph(map: Map<String, Entity>, execLast: boolean, target: number[]): number[][] {
        const n = 11; // 坐标系的范围是 0 <= x <= 10, 0 <= y <= 10
        const graph: number[][] = new Array(n * n).fill(Infinity).map(() => new Array(n * n).fill(Infinity));

        // 构建图的连接关系
        for (let x = 0; x < n; x++) {
            for (let y = 0; y < n; y++) {
                const index = x * n + y; // 计算节点在邻接矩阵中的索引

                // 判断当前坐标下的节点是否存在 Entity
                if (this.hasEntity(x, y, map, execLast, target)) {
                    continue; // 如果存在 Entity，则表示该节点不通，跳过连接关系的构建
                }

                // 构建当前节点与相邻节点的连接关系
                if (x > 0 && !this.hasEntity(x - 1, y, map, execLast, target)) {
                    graph[index][index - n] = 1; // 左侧节点与当前节点连通，距离为 1
                }
                if (x < n - 1 && !this.hasEntity(x + 1, y, map, execLast, target)) {
                    graph[index][index + n] = 1; // 右侧节点与当前节点连通，距离为 1
                }
                if (y > 0 && !this.hasEntity(x, y - 1, map, execLast, target)) {
                    graph[index][index - 1] = 1; // 上方节点与当前节点连通，距离为 1
                }
                if (y < n - 1 && !this.hasEntity(x, y + 1, map, execLast, target)) {
                    graph[index][index + 1] = 1; // 下方节点与当前节点连通，距离为 1
                }
            }
        }
        return graph;
    }

    static hasEntity(x: number, y: number, map: Map<String, Entity>, execLast: boolean, target: number[]): boolean {
        // 根据坐标判断该节点是否存在 Entity，根据实际情况进行实现
        // 返回 true 表示该节点存在 Entity，不通；返回 false 表示该节点可通行
        const index = x + '-' + y;
        if (execLast && index === target[0] + '-' + target[1]) {
            return false
        }
        return map.has(index);
    }

    static dijkstra(graph: number[][], start: number, end: number): number[] {
        const n = graph.length; // 节点数量
        const dist: number[] = new Array(n).fill(Infinity); // 起点到各个节点的最短距离
        const visited: boolean[] = new Array(n).fill(false); // 记录已经确定最短路径的节点
        const prev: number[] = new Array(n).fill(-1); // 记录最短路径中节点的前驱节点

        dist[start] = 0; // 起点到自身的距离为0

        for (let i = 0; i < n; i++) {
            const u = this.getMinDistance(dist, visited); // 选择一个距离最小且不在visited中的节点
            visited[u] = true; // 将该节点加入visited

            if (u === end) {
                break; // 如果当前节点是终点，则已找到最短路径，退出循环
            }

            for (let v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] !== 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v]; // 更新最短距离
                    prev[v] = u; // 更新前驱节点
                }
            }
        }

        return this.getPath(prev, start, end);
    }

    static getMinDistance(dist: number[], visited: boolean[]): number {
        let minDist = Infinity;
        let minIndex = -1;

        for (let i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    static getPath(prev: number[], start: number, end: number): number[] {
        const path: number[] = [];
        let current = end;

        while (current !== -1) {
            path.unshift(current);
            current = prev[current];
        }

        return path;
    }

}